/*
* Insertion sort is a simple sorting algorithm that is relatively efficient for
* small lists and mostly-sorted lists, and often is used as part of more sophisticated 
* algorithms. It works by taking elements from the list one by one and inserting them 
* in their correct position into a new sorted list. In arrays, the new list and the 
* remaining elements can share the array's space, but insertion is expensive, requiring 
* shifting all following elements over by one. The insertion sort works just like its 
* name suggests - it inserts each item into its proper place in the final list. 
* The simplest implementation of this requires two list structures - the source list and 
* the list into which sorted items are inserted. To save memory, most implementations use 
* an in-place sort that works by moving the current item past the already sorted items and 
* repeatedly swapping it with the preceding item until it is in place. Shell sort (see below)
* is a variant of insertion sort that is more efficient for larger lists. This method is 
* much more efficient than the bubble sort, though it has more constraints.
*
*/

#include <iostream>
using namespace std;

int main(){
	int a[]={20,2,3,9,1,50,10,5};
	int n=sizeof(a)/sizeof(int);
	for(int i=1;i<n;i++){
		int j=i;
		int tmp = a[j];
		for(j=i; j>0 && a[j-1] > tmp; j--)
			a[j]=a[j-1];

		a[j]=tmp;    
	}

	for(int i=0;i<n;i++){
		cout<<a[i]<<endl;
	}
}
